package com.algorithm.ch1.cjm.tree;

/**
 * 对称二叉树
 * <p>
 * 给定一个二叉树，检查它是否是镜像对称的。
 * <p>
 * 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
 * <p>
 * 1
 * / \
 * 2   2
 * / \ / \
 * 3  4 4  3
 * 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
 * <p>
 * 1
 * / \
 * 2   2
 * \   \
 * 3    3
 */
import com.algorithm.ch1.cjm.tree.model.TreeNode;

public class IsSymmetric {

    /**
     * 递归法
     * 递归法的本质就是找出，可以独立出来的一个独立个体，如果通过自己调用自己来解决复杂问题
     * 本题中：
     * 首先判断他的左右节点相等。
     * 然后再判断左右节点的下一级节点对称相等
     * 下一级四个子节点又可以组成两个模型
     *
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {

        if(root == null){
            return true;
        }

        boolean flag = isTreeSymmertic(root.left, root.right);

        return flag;
    }

    public boolean isTreeSymmertic(TreeNode left, TreeNode right){

        if(left == null && right == null) {
            return true;
        }

        if(left == null) {
            return false;
        }

        if(right == null) {
            return false;
        }

        boolean flag = left.val == right.val;
        boolean flag1 = isTreeSymmertic(left.left, right.right) && isTreeSymmertic(left.right, right.left);

        return flag && flag1;
    }

}
